#include <cstddef> // for NULL
struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
class Solution
{
public:
    // 思路：先找到相遇点，然后让快指针从头开始一步一步的走，slow从当前位置开始走，直到2个相遇就是环的入口
    ListNode *detectCycle(ListNode *head)
    {
        ListNode *slow = head;
        ListNode *fast = head;
        while (fast && fast->next) // 找到相遇点
        {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) //    如果相遇，说明有环
                break;
        }
        if (!fast || !fast->next) // 判断是否有环
            return NULL;
        fast = head;         // 让快指针从头开始走
        while (fast != slow) // 直到相遇
        {
            slow = slow->next;
            fast = fast->next;
        }
        return slow;
    }
};